HPAVC/HPAVC CD-ROM.iso/pc/FAQSYS18.ZIP/FAQS.DAT/OTMPHONG.DOC

Text File | 1995-04-08 | 23.4 KB | 516 lines

        OTMPHONG.DOC - A new approximation technique for the Phong
                       shading model based on linear interpolation
                       of angles

        released 3-30-95
        by Voltaire/OTM [Zach Mortensen]

        email -
        [e-mail]

        IRC -
        Volt in #otm, #coders


INTRODUCTION

                Realtime phong shading has always been a goal for 3d
        coders, however the massive amount of calculations involved
        has (until recently) hampered progress in this area.  When I
        first heard the term 'realtime phong shading' mentioned about 6
        months ago, I laughed to myself at what I perceived was an
        oxymoron.  In my experience at the time (derived from reading
        several 3d documents), phong shading required a tremendous
        amount of interpolation and one square root per pixel.  Even
        with lookup tables for the square root function, there was no
        way that this algorithm would be fast enough to use in
        realtime.  Early reports from other coders attempting realtime
        phong shading proved this, the fastest code I heard of could
        draw around 1500 triangles per second.

                Phong shading never really was a goal of mine.  I am a
        pretty lazy person, I could think of a thousand ways I would
        rather spend my time than implementing an inherently slow
        algorithm in my code and trying to optimize it.  Until about a
        week ago that is, when I received a little demo called CHEERIO
        by Phred/OTM.  Phred and I have been good friends for quite
        awhile, and we both write vector code.  We have helped each
        other improve the speed of our code dramatically by sharing our
        ideas, 2 heads are definitely better than 1!  Anyway, there
        were rumors flying around that CHEERIO was phong shaded, when
        in reality it was really nice gouraud shading.  I took a close
        look and...well, it looked like phong but Phred wasn't around
        to correct us, so I went on believing he had coded a phong fill
        that was as fast as my gouraud fill.  Part of the reason Phred
        and I have made our code so fast is competition, neither of us
        can stand being outdone by the other.  So whether I wanted to
        or not, I had to come up with a fast phong fill SOON if I were
        to save face.

                The fastest method I knew of was using a Taylor series
        to approximate color values.  This method involves a fairly
        fast inner loop with a lot of precalculation.  It also requires
        a thorough knowledge of calculus.  Believe me, doing Taylor
        series on your homework is a lot easier than trying to
        implement one in the real world for some strange reason.  So
        that is where I started, I was deriving the Taylor
        approximation for phong shading when I stumbled upon what
        seemed to me an obvious shortcut that would make phong filling
        nearly as fast as gouraud filling.  I also believe I am the
        first to come up with this method, since I have seen no
        articles about it, and I have yet to see realtime phong shading
        in a demo or game.

                OK, now on to the fun stuff...



THE PHONG ILLUMINATION MODEL


                This is not a text on phong illumination, but on phong
        SHADING.  They are two very different things.  Whether you use
        phong shading or not, you can use phong illumination with your
        lambert or gouraud shading to make your colors look more
        realistic.  I don't want to get into how this formula is
        derived, so I will just give you the low down dirty goods.


        color = specular + (cos x) * diffuse + (cos x)^n * specular


                Make sure you set up your palette in this way. In a
        nutshell, the ambient component defines the color of an object
        when no light is directly striking it, the diffuse component
        defines the color of the object, and the specular component
        defines the color of the highlight made when light strikes the
        object directly.  x should have a range of 0 to 90 degrees,
        since that is the range of angles possible when light
        intersects a visible plane.  The power n in the specular
        component defines certain attributes about the material, the
        greater the power n, the shinier the material will appear to be
        (i.e. the specular highlight will be smaller and brighter as n
        increases).



THE PHONG SHADING MODEL


                The idea behind phong shading is to find the exact
        color value of each pixel.  In its most common form, the phong
        shading model is as follows:

        1) determine a normal vector at each vertex of a polygon, the
           same normal vector used in gouraud shading.

        2) interpolate normal vectors along the edges of the polygon.

        3) interpolate normal vectors across each scanline, so you have
           one normal vector for each pixel in the polygon.

        3) determine the color at each pixel using the dot product of
           the normal vector at that pixel and the light vector, the
           same method used in gouraud and lambert shading.  Since the
           interpolated normals are not of constant length, this step
           requires a square root to find the length of the normal.


                This shading model produces impressive results.  A new
        color is calculated for each pixel, and the color gradient
        across a plane is non linear.

                However it is also VERY SLOW if implemented as it is
        shown here.  In order to linearly interpolate a vector, one
        must interpolate x, y, and z coordinates.  This task is not
        nearly as time consuming as the dot product, which requires 4
        multiplies, 2 adds, a divide and a square root per PIXEL.  A
        few optimizations can be performed that eliminate one multiply
        and replace the square root with a table lookup, but 3
        multiplies and a divide per pixel are far too slow to be used
        in realtime.


OPTIMIZING THE PHONG SHADING MODEL


                Lets mathematically break down the phong shading model.
        After all is said and done, you are left with the dot product
        of the pixel normal vector and the light vector divided by the
        product of the magnitudes of these two vectors.  Another way to
        express this value is (cos Θ), where Θ is the smallest angle
        between the two vectors.

        u = pixel normal vector
        v = light vector

        u dot v = cos Θ * |u| * |v|

                 u dot v
        cos Θ = ---------
                |u| * |v|

                So the dot product of a normal vector and a light vector
        divided by the product of the magnitudes of the two vectors is equal
        to the cosine of the smallest angle between the two vectors.  This
        should be nothing new, it is the same technique used to find color
        values in the lambert and gouraud shading techniques.  Lets attempt
        to graphically represent what is going on with phong, gouraud and
        lambert shading.


                                graph of y = cos Θ (*)
        |
        |
        |*    *
        |          *
        |             *
        |                *
        |                   *
        |                     *
        |                       *
        |                         *
      y |                          *
        |                           *
        |                            *
        |                             *
        |                              *
        |                               *
        |                                *
        |                                 *
        |                                  *
        |                                   *
        +------------------------------------------
                            Θ

                The phong shading model states that the intensity of light
        at a given point is given by the dot product of the light and normal
        vectors divided by the product of the magnitudes of the two vectors.
        Flat shading is the roughest approximation of this, planes are
        rendered in a single color which is determined by the cosine of the
        angle between the plane's normal vector and the light vector.  If
        we graph the intensity of light striking flat shaded planes, we
        should find that they roughly form a cosine curve, since the color
        values at certain points are determined by the cosine of the angle
        between two vectors


                          graph of Intensity = cos Θ (*)
        |      flat shading approximations of light intensity shown as (X)
        |
        |*XXXX*XX               dΘ  (angle between normal vectors)
        |          *       -------------
        |        XXXXX*XXXX            |
        |                *             | dI  (change in intensity)
        |                   *          |
        |                  XXX*XXXXXX  |
        |                       *
      I |                         *
        |                          *
        |                           *XXXXXX
        |                            *
        |                             *
        |                              *
        |                               *
        |                                *
        |                                 *XXXXX
        |                                  *
        |                                   *
        +------------------------------------------
                             Θ

                This graph tells us something that we already know by
        practical experience, that flat shading is very inaccurate for large
        values of dΘ, and much more accurate for small values of dΘ.  This
        means that the shading appears smoother when the angle between
        normals (and therefore between planes) is very small.

                Now lets consider gouraud shading.  Gouraud shading is a
        linear interpolation of color between known intensities of light.
        The known intensities in gouraud shading are defined at each
        vertex, once again by use of the dot product.  In this case, the
        normal vector at each polygon vertex is the average of the normal
        vectors (the ones used in flat shading) for all planes which share
        that vertex.  Normals of planes which are greater than 90 and less
        than 270 degrees from the plane containing the vertex in question are
        not considered in the average because the two planes are facing
        away from each other.  If we plot interpolated intensities used in
        gouraud shading against the cosine curve, it is evident that gouraud
        shading is a much more accurate approximation than flat shading.


                        graph of Intensity = cos Θ (*)
        |        interpolated light intensities shown as (X)
        | ---------------------------------+
        |*X   *                            | in this region, the linear
        |  XXXX ---*--------+              | approximation is always going to
        |      XXX    *     | dI (error)   | be inaccurate without a very
        |         XXXX --*--+              | small value for dΘ
        |             XXX   *              |
        |                XXXXX*  --------------+
        ||____________________|X*              |
      I |        dΘ              X*            |
        |                         X*           | in this region, a gouraud
        |                          X*          | approximation is nearly
        |                           X*         | perfect because cos x is
        |                            X*        | nearly linear
        |                             X*       |
        |                              X*      |
        |                               X*     |
        |                                X*    |
        |                                 X*   |
        |                                  X*  |
        +------------------------------------------
                           Θ

                This graph tells us that gouraud shading is very accurate
        as Θ->90.  However, if Θ is small and dΘ is large, gouraud shading
        will look like an obvious linear approximation.  This can be avoided
        by using smaller values of dΘ (i.e. use more polygons to fill in the
        gaps in the interpolation).  With enough polygons, gouraud shading
        can be 100% correct.

                Phong shading is the most correct method of shading because
        it is not an approximation, distinct colors are determined for each
        pixel.  These values follow the cosine curve exactly, because the
        intensity of each pixel was calculated using a dot product, which
        eventually yields the cosine of the angle between the plane at
        that pixel and the light vector.  If we plot phong shading
        intensities with the cosine curve, we find that the values
        follow the function exactly.


                        graph of Intensity = cos Θ (*)
        |            phong light intensities shown as (X)
        |
        |X    X
        |          X
        |             X
        |                X
        |                   X
        |                     X
        |                       X
        |                         X
      I |                          X
        |                           X
        |                            X
        |                             X
        |                              X
        |                               X
        |                                X
        |                                 X
        |                                  X
        |                                   X
        +------------------------------------------
                             Θ

                Once again, shadings calculated using the phong model follow
        the cosine curve, because the dot product between the normal vector
        at each pixel and the light vector can be simplified to a function
        involving cos Θ.


TAYLOR APPROXIMATIONS

                Now that we know a function which gives the intensity of
        light at a given pixel, we need to find a fast way to evaluate that
        function.  Most people seem to know that Taylor series can be used
        for phong shading, but I have never met anyone that was able to
        tell me that the cosine function would be the function that is
        approximated.  The fact that vector coders are afraid of math is
        disturbing to me.

                The Taylor approximation for cos(x) is given by the following
        series:

                    x^2   x^4   x^6                      x^(2n)
        cos x = x - --- + --- - --- + ... + (-1)^(n-1) * ------
                     2!    4!    6!                       (2n)!

        Actually I think that is a Maclaurin series, which is nothing more
        than a Taylor series expanded about the point x = 0.  In any case,
        you can use any number of terms in a Taylor series to approximate
        a function.  The more terms you use, the more accurate your
        approximation will be...and the slower your approximation will be.
        The first two terms of the series for cos x are sufficient to give
        an accurate approximation from x = 0 to x = 90, which are the limits
        of Θ between the light and visible facets.

                This is about as far as I got with the Taylor approximation
        method for phong shading.  Once I got to this point, the proverbial
        light bulb clicked on inside my head, and I forgot all about Taylor
        series because I came up with a faster method.


LINEAR INTERPOLATION OF ANGLES

                To set the scene for you, I was riding the bus to school
        about at about 8:00 in the morning when I thought I would do a bit
        of work on the phong algorithm.  The bus ride is about 30 minutes and
        is usually devoid of any excitement, so I whipped out my trust pad
        of graph paper and started grinding out formulas.  I got really
        excited when I arrived at the Taylor approximation, but I just about
        jumped through the roof when this thought entered my mind.

                I realized that the Taylor approximation for phong shading
        basically interpolates values along the curve I = cos(Θ) just as
        gouraud shading linearly interpolates values, except the values for
        phong shading happen to fall directly ON the cosine curve.  The
        problem is that the cosine curve is not linear, therefore phong
        interpolation is much more complicated than gouraud interpolation.

                Then I stepped back and looked at the problem from another
        angle (punny).  If it were possible to interpolate some other value
        related to cos(Θ), and if this other value changed in a linear
        fashion, it would be possible to create a lookup table that related
        cos(Θ) to this other value.  After a bit of deep thinking, I realized
        that I was staring right at such a value, Θ!  The angle between the
        light vector and the normal vector at each vertex of a plane
        changes in a linear fashion as you go from one vertex to the next, and
        from one edge of the plane to the next across each scanline.

                As soon as it hit me, this idea made perfect sense.  The phong
        shading model calls for normal vectors to be linearly interpolated
        from vertex to vertex and from edge to edge.  When I thought about
        this a bit further, it seemed totally ridiculous.  The actual
        <x,y,z> coordinates of these normals do not matter one bit, only
        the angle between the vector defined by these coordinates and the
        light vector.  Why interpolate 3 coordinates per pixel when they are
        just an intermediate step in finding the angle between two vectors?

                So angular interpolation eliminates the interpolation of a
        whole vector.  But that's not all, it also eliminates the dot product
        which was previously needed to find the cosine of the angle between
        the normals and the light.  Without the dot product or vector
        interpolation,  there is nothing left of the traditional method of
        phong shading.  All that needs to be done is interpolate angles
        across the plane, and look up the cosine of those angles in a lookup
        table.  Once you know the cosine, the rest is easy.

                Using this method, an existing gouraud fill can be converted
        to a phong fill very very easily.  Instead of interpolating colors
        across the plane, interpolate angles instead.  If you are smart about
        the way you express your angles, they can be represented in a single
        byte.  Remember that the only possible values for the smallest angle
        between a normal vector and a light vector are 0 to 90 degrees.

                After you have interpolated an angle and looked up its
        cosine, all you need to do is plot a pixel of the correct color.
        The color calculations for each pixel are the same as those for
        lambert and gouraud shading.  Multiply the cosine by the number of
        colors in the gradated palette range and add the result to the base
        color of the range.

                Of course, you need to determine the angle between the light
        and the normal vectors at each vertex.  This can be accomplished by
        the inverse cosine function.  By taking the inverse cosine of the
        cosine, you get the angle as a result.  Try to remember your trig
        classes.


LIMITATIONS

                Angular interpolation is correct in 99% of all possible
        cases.  The only cases when it will not be correct is when the
        angles at any two or more vertices are equal.  Interpolated vector
        phong shading will display a specular highlight inside the plane in
        such a case, but interpolated angle phong shading will render the
        plane in a solid color because the difference between the angles at
        the vertices is 0, there will be no change in the angle across the
        plane.


CRITICISM AND RESPONSE SESSION

                The preliminary release of demos incorporating this technique
        were met with a bit of criticism, most of which was caused by
        ignorance.  Here are a few common criticisms of this technique and
        my responses.


        "You are interpolating something linearly, and linear interpolation
        is gouraud shading"

        Do your homework.  The phong model calls for linear interpolation of
        normal vectors, and it is obviously not gouraud shading.


        "It looks a lot like gouraud shading"

        Yes it does.  Refer to the section where I plotted intensities based
        on various shading techniques, and take a look at the graphs of
        Intensity vs. Θ.  You will find that for a small dΘ, gouraud shading
        looks very much like phong shading.  However, phong shading can
        achieve this result with a much larger dΘ, which means less facets.


        "I see no specular highlight"

        The first version I released used a linear palette, not a palette
        based on the phong illumination model.  Without the phong
        illumination model, it is very hard to make specular highlights look
        correct.  The palette has now been corrected to conform to the phong
        illumination model.


        "You still can't get a highlight in the center of a single polygon"

        Well, I think that the speed of this method is a reasonable tradeoff.
        Specular highlights appear between polygons with this method, and
        the difference is not too noticeable.


        "The specular highlights are no different than gouraud specular
         highlights"

        Take a closer look.  With gouraud shading, specular highlights are
        gradated in a linear manner.  With phong shading, the gradation of
        colors is nonlinear because it follows the cosine curve.


CLOSING COMMENTS

                Angular interpolated phong shading is new as far as I know.
        If you decide to use this technique in any of your code, please give
        me appropriate credit.  I am not asking for a cut of your royalties,
        just to have my name mentioned somewhere.  I have always made it a
        point to give credit where credit is due, and I would appreciate if
        you would do the same.  Someone along the line actually has to put in
        some hard work to develop the algorithms that we all use.


GREETS

        Siri                    - you are the love of my life
        OTM                     - I...have...nothing...to...say
        Phred/OTM               - good vector conversation
        Rich Beerman            - our game will rule
        Darkshade               - for always being helpful
        THEFAKER/S!P            - infinite humility :)
        Sami Nopanen            - cacheman...
        Tran and Daredevil      - PMODE/W, gotta love it
        VLA                     - for not releasing any more 3d docs :)

        all my #coders buddies
        bri_acid
        MainFrame
        StarScream
        ae-
        fysx
        phoebus
        doom
        Moomin
        Simm
        LiveFire
        MArtist
        Zed-
        Omni
        ior
        Kodiak_
        Saeger
        anixter
        Hasty

        and everyone else I forgot...